package com.ly.algorithm.InterviewProblem.ByteDance;


import org.junit.jupiter.api.Test;

/**
 * @Classname ByteDance01
 * @Description
 *
 *
 * 给定一个链表，此链表奇数位为升序排列，偶数位为降序排列。
 * 现在要求排成全局升序
 * 输入：1->200->10->120->30->8->88->4
 * 输出：1->4->8->10->30->88->120->200
 *
 *
 *
 * @Date 2021/1/28 17:06
 * @Author 冷心影翼
 */
public class ByteDance01 {


    @Test
    public void Solution() {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(200);
        listNode.next.next = new ListNode(10);
        listNode.next.next.next = new ListNode(120);
        listNode.next.next.next.next = new ListNode(30);
        listNode.next.next.next.next.next = new ListNode(8);
        listNode.next.next.next.next.next.next = new ListNode(88);
        listNode.next.next.next.next.next.next.next = new ListNode(4);
        System.out.println(sortLinkedList(listNode));
    }

    public ListNode sortLinkedList(ListNode head) {
        ListNode l1 = head;
        ListNode l2 = head.next;
        if(l2 == null) {
            return head;
        }
        //拆分
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        while (cur1.next!=null && cur2.next!= null) {
            cur1.next = cur1.next.next;
            cur1 = cur1.next;
            cur2.next = cur2.next.next;
            cur2 = cur2.next;
        }
        cur1.next = null;
        //翻转l2
        ListNode h = new ListNode(-1);
        while (l2!=null) {
            ListNode next = l2.next;
            l2.next = h.next;
            h.next = l2;
            l2 = next;
        }
        //合并l1,l2
        ListNode r = new ListNode(-1);
        ListNode pre = r;
        l2 = h.next;
        while (l1 != null && l2!= null) {
            if(l2.val > l1.val) {
                pre.next = l1;
                l1 = l1.next;
            }else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        pre.next = l1==null?l2:l1;
        return r.next;
    }

    class ListNode {
        ListNode next;
        int val;

        public ListNode(int val) {
            this.val = val;
        }
    }
}

